package com.wxc.rbtree;

import java.util.NoSuchElementException;

/**
 * @program: LoveDataStructures1
 * @description: 二叉搜索树
 * @author: wxc
 * @create: 2021-07-24 22:55
 **/
public class BinarySearchTree<E> extends BinaryTree<E> {

    protected IComparator<E> comparator;

    public BinarySearchTree(IComparator<E> comparator) {
        this.comparator = comparator;
    }

    public BinarySearchTree() {
    }

    private void elementNotNullCheck(E element) {
        if (element == null) throw new IllegalArgumentException("element must not be null");
    }

    public void add(E element) {
        elementNotNullCheck(element);
        if (root == null) {
            root = createNode(element, null, null, null);
            size++;
            afterAdd(root);
            // 就一个结点不需要旋转
            return;
        }
        // 递归实现方式
//        add(element,root);
        // 循环实现方式
        Node<E> node = root;
        Node<E> parent = root;
        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.element);
            // 父结点
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                // 相等
                node.element = element;
                return;
            }
        }
        Node<E> newNode = createNode(element, null, null, parent);
        if (cmp > 0) parent.right = newNode;
        else parent.left = newNode;
        size++;
        // 旋转
        afterAdd(newNode);
    }

    protected Node<E> createNode(E element, Node<E> left, Node<E> right, Node<E> parent) {
        return new Node<>(element, left, right, parent);
    }

    protected void afterAdd(Node<E> node) {

    }
//    private void add(E element, Node<E> node) {
//        int cmp = compare(element, node.element);
//        if (cmp < 0) {
//            if (node.left != null) {
//                add(element, node.left);
//            } else {
//                node.left = new Node<>(element, null, null, node);
//            }
//        } else {
//            if (node.right != null) {
//                add(element, node.right);
//            } else {
//                node.right = new Node<>(element, null, null, node);
//            }
//        }
//    }

    /*
     * @param
     * @author wxc
     * @return
     * @Description: element1 > element2 则 return > 0 || element1 < element2 则 return < 0
     */
    private int compare(E element1, E element2) {
        if (comparator != null) return comparator.compareTo(element1, element2);
        // 如果使用自定义比较器的话，那泛型E是没必要实现Comparable接口的，但是在这里就需要强制转型，因为上面没走进去
        if (element1 instanceof Comparable) return ((Comparable) element1).compareTo(element2);
        throw new ClassCastException("not implements Comparable interface");
    }

    /*
     * @param
     * @author wxc
     * @return
     * @Description: 删除一个结点 P122 P123
     */
    public void remove(E element) {
        remove(getNode(element, root));
    }

    private void remove(Node<E> node) {
        size--;
        // 度为2
        if (node.hasFullChild()) {
            // 后继
            Node<E> nextNode = getSuccessor(node);
            // 覆盖
            node.element = nextNode.element;
            // 删除 nextNode 这步太妙了
            node = nextNode;
        }
        // 度为0
        if (node.isLeaf()) {
            // 根结点
            if (node.parent == null) {
                root = null;
            }
            // 不是根结点
            else {
                if (node.parent.left == node) node.parent.left = null;
                else node.parent.right = null;
            }
            // 删除的是叶子结点 所以取代被删除的结点是null
            afterRemove(node,null);
        }
        // 度为1
        else {
            // 左边取代node
            if (node.left != null) {
                node.left.parent = node.parent;
                //          A           A
                //       (B)    ->    C
                //      C
                if (node.parent == null) {
                    root = node.left;
                    afterRemove(node,root);
                    return;
                }
                if (node == node.parent.left) node.parent.left = node.left;
                    //          A              A
                    //              (B)    ->    C
                    //            C
                else node.parent.right = node.left;

                afterRemove(node,node.left);
            }
            // 右边取代node
            else {
                node.right.parent = node.parent;

                if (node.parent == null) {
                    root = node.right;
                    afterRemove(node,root);
                    return;
                }
                if (node == node.parent.left) node.parent.left = node.right;
                else node.parent.right = node.right;

                afterRemove(node,node.right);
            }
        }
    }

    // node: 删除的结点
    // replaceNode: 取代的结点
    protected void afterRemove(Node<E> node,Node<E> replaceNode) {

    }

    private Node<E> getNode(E element, Node<E> node) throws NoSuchElementException {

        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                return node;
            }
        }
        throw new NoSuchElementException("not find this element");
    }

    public boolean contains(E element) {
        Node<E> node;
        try {
            node = getNode(element, root);
        } catch (NoSuchElementException e) {
            node = null;
        }
        return node != null;
    }

}
